'''
# Apriori算法：
Apriori算法是一种用于发现数据集中频繁项集的经典算法，通常用于关联规则挖掘任务，特别是在市场篮分析中。该算法的核心思想是利用频繁项集的性质来降低搜索空间的复杂度。

# 相关概念：
频繁项集（Frequent Itemsets）：在一个数据集中经常出现在一起的物品集合称为频繁项集。频繁项集通常用支持度来衡量，即包含该项集的事务的比例。
关联规则（Association Rules）：形如{A} -> {B}的规则，表示如果一笔交易包含物品集合A，则它也很可能包含物品集合B。

# 算法步骤：
1. 生成候选项集：
   - 首先，扫描整个数据集，统计每个单个项的支持度。
   - 根据最小支持度阈值（用户定义的阈值），剔除支持度低于阈值的项，得到频繁1项集。
2. 迭代生成更高阶的频繁项集：
   - 基于频繁k-1项集，通过连接操作产生候选k项集。
   - 再次扫描数据集，计算候选k项集的支持度。
   - 剔除支持度低于阈值的候选项集，得到频繁k项集。
3. 提取关联规则：
   - 根据频繁项集，生成可能的关联规则。
   - 计算每个关联规则的置信度，剔除低于用户指定置信度阈值的规则。
   - 返回频繁项集和关联规则。

# 算法特点：
1. Apriori算法利用了频繁项集的Apriori性质，即如果一个项集是频繁的，则它的所有子集也是频繁的。
2. 通过剪枝操作，减少了候选项集的生成和计数过程中的计算量，提高了算法的效率。
'''

import pandas
import os
import matplotlib.pyplot as plt
import numpy as np


def createC1(dataSet):
   '''
   创建候选项集C1
   '''
   C1 = []
   for transaction in dataSet:
       for item in transaction:
           if not [item] in C1:
               C1.append([item]) #store all the item unrepeatly

   C1.sort()
   #return map(frozenset, C1)#frozen set, user can't change it.
   return list(map(frozenset, C1))

def scanD(D,Ck,minSupport):
   '''
   扫描数据集，返回满足最小支持度的候选项集列表
   参数：数据集、候选项集列表 Ck以及感兴趣项集的最小支持度 minSupport
   '''
   ssCnt={}
   for tid in D:#遍历数据集
       for can in Ck:#遍历候选项
           if can.issubset(tid):#判断候选项中是否含数据集的各项
               #if not ssCnt.has_key(can): # python3 can not support
               if not can in ssCnt:
                   ssCnt[can]=1 #不含设为1
               else: ssCnt[can]+=1#有则计数加1
   numItems=float(len(D))#数据集大小
   retList = []#L1初始化
   supportData = {}#记录候选项中各个数据的支持度
   for key in ssCnt:
       support = ssCnt[key]/numItems#计算支持度
       if support >= minSupport:
           retList.insert(0,key)#满足条件加入L1中
       supportData[key] = support
   return retList, supportData

def aprioriGen(Lk, k): #组合，向上合并
   '''
   生成候选项集列表
   参数：频繁项集列表 Lk 与项集元素个数 k
   '''
   retList = []
   lenLk = len(Lk)
   for i in range(lenLk):
       for j in range(i+1, lenLk): #两两组合遍历
           L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
           L1.sort(); L2.sort()
           if L1==L2: #若两个集合的前k-2个项相同时,则将两个集合合并
               retList.append(Lk[i] | Lk[j]) #set union
   return retList

def apriori(dataSet, minSupport = 0.5, n=3):
   '''
   Apriori算法
   参数：数据集、最小支持度、项集元素个数
   返回：频繁项集列表、包含那些频繁项集支持数据的字典
   '''
   C1 = createC1(dataSet)
   D = list(map(set, dataSet)) #python3
   L1, supportData = scanD(D, C1, minSupport)#单项最小支持度判断 0.5，生成L1
   L = [L1]

   #创建包含更大项集的更大列表,直到下一个大的项集为空
   for k in range(2, n+2):
       Ck = aprioriGen(L[k-2], k)#Ck
       Lk, supK = scanD(D, Ck, minSupport)#get Lk
       supportData.update(supK)
       L.append(Lk)

   return L, supportData

def generateRules(L, supportData, minConf=0.7):
   '''
   生成关联规则
   参数：频繁项集列表、包含那些频繁项集支持数据的字典、最小可信度
   返回：关联规则列表
   '''
   bigRuleList = [] #存储所有的关联规则
   for i in range(1, len(L)):  #只获取有两个或者更多集合的项目，从1,即第二个元素开始，L[0]是单个元素的
       # 两个及以上的才可能有关联一说，单个元素的项集不存在关联问题
       for freqSet in L[i]:
           H1 = [frozenset([item]) for item in freqSet]
           #该函数遍历L中的每一个频繁项集并对每个频繁项集创建只包含单个元素集合的列表H1
           if (i > 1):
           #如果频繁项集元素数目超过2,那么会考虑对它做进一步的合并
               rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
           else:#第一层时，后件数为1
               calcConf(freqSet, H1, supportData, bigRuleList, minConf)# 调用函数2
   return bigRuleList

def calcConf(freqSet, H, supportData, brl, minConf=0.7):
   '''
   计算可信度
   参数：频繁项集、H1、包含那些频繁项集支持数据的字典、规则列表、最小可信度阈值
   '''
   prunedH = []#返回一个满足最小可信度要求的规则列表
   for conseq in H:#后件，遍历 H中的所有项集并计算它们的可信度值
       conf = supportData[freqSet]/supportData[freqSet-conseq] #可信度计算，结合支持度数据
       if conf >= minConf:
        #    print (freqSet-conseq,'-->',conseq,'conf:',conf)
           #如果某条规则满足最小可信度值,那么将这些规则输出到屏幕显示
           brl.append((freqSet-conseq, conseq, conf))#添加到规则里，brl 是前面通过检查的 bigRuleList
           prunedH.append(conseq)#同样需要放入列表到后面检查
   return prunedH


def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
   '''
   递归检查
   参数：频繁项集、H1、包含那些频繁项集支持数据的字典、规则列表、最小可信度阈值
   '''
   m = len(H[0])
   if (len(freqSet) > (m + 1)): #频繁项集元素数目大于单个集合的元素数
       Hmp1 = aprioriGen(H, m+1)#存在不同顺序、元素相同的集合，合并具有相同部分的集合
       Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)#计算可信度
       if (len(Hmp1) > 1):    
       #满足最小可信度要求的规则列表多于1,则递归来判断是否可以进一步组合这些规则
           rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf) 


if __name__ == '__main__':

    # dataset = [
    #     ['苹果', '香蕉', '橙子', '西瓜'],
    #     ['苹果', '香蕉', '橙子'],
    #     ['苹果', '香蕉'],
    #     ['苹果', '橙子'],
    #     ['苹果', '西瓜'],
    #     ['香蕉', '橙子'],
    #     ['香蕉', '西瓜'],
    #     ['橙子', '西瓜'],
    # ]

    # 探究 Team 的特色项目
    # 对 Team 和 Event 字段进行关联性分析
    baseDir = './2025_Problem_C_Data'
    dataset = pandas.read_csv(os.path.join(baseDir, 'summerOly_athletes.csv'), encoding='utf-8', low_memory=False)
    dataset = dataset[dataset['Medal'] != 'No medal']
    dataset = dataset[dataset['Year'] == 2024]
    dataset = dataset[['NOC', 'Sport']].to_numpy().tolist()

    # 创建关联规则
    L, supportData = apriori(dataset, minSupport=0.005, n=3)
    result = generateRules(L, supportData, minConf=0.1)

    # 格式化输出关联规则
    for i in result:
        print(f'{set(i[0])} ----> {set(i[1])}, 置信度: {i[2]}')



